/* probabilistic similarity of states */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

#include "itf_debug.h"

#include "dlinkedlist.h"
#include "prefix_tree.h"
#include "alg_pss.h"
#include "mex.h"

/* macro-generating functions of the cluster list */
GEN_DLINKEDLIST_FUNCTIONS(dll_cluster, cluster_l, cluster_n, cluster_el);
/* --- */

/* */
GEN_DLINKEDLIST_FUNCTIONS(dll_setnt, setnt_l, setnt_n, ntrieNode *);
/* */


/* Start matlab Funtions                                                 */
/* --------------------------------------------------------------------- */
static void K_S_test(double *clkarray1, unsigned int clk1_size, double *clkarray2, unsigned int clk2_size, double alpha, double *h, double *p, double *k) {
    
    mxArray *input[3], *out[3];
    double *clk1, *clk2, *al;
    
    input[0] =  mxCreateDoubleMatrix(1, clk1_size, mxCOMPLEX);
    input[1] =  mxCreateDoubleMatrix(1, clk2_size, mxCOMPLEX);
    input[2] =  mxCreateDoubleMatrix(1, 1, mxCOMPLEX);
    
    clk1 = (double *) mxGetData(input[0]);
    clk2 = (double *) mxGetData(input[1]);
    al   = (double *) mxGetData(input[2]);
    
    /*Copy clkarray1 to clk1*/
    memcpy(clk1, clkarray1, clk1_size*sizeof(double));
    /*Copy clkarray2 to clk2*/
    memcpy(clk2, clkarray2, clk2_size*sizeof(double));
    
    *al = alpha;
    
    /* Call the Matlab funtion '[h,p,k] = kstest2(x,y,alpha)' */
    mexCallMATLAB(3, out, 3, input, "kstest2");
    
    *h = * (double *) mxGetData(out[0]);
    *p = * (double *) mxGetData(out[1]);
    *k = * (double *) mxGetData(out[2]);
}
/* --------------------------------------------------------------------- */
/* End matlab Funtions                                                   */

void replace_inward(inward_l *inlist, ntrieNode *rpl, ntrieNode *new) {
    inward_n *in;
    
    for(in = inlist->firstNode; in != NULL; in=in->next) {
        if(in->data == rpl) {
            in->data = new;
            break;
        }
    }
    
    dll_inward_insertend(inlist, dll_inward_newnode(new));
    /*mexErrMsgTxt("Replace error\n");*/
}

evnode *get_equal_node(evnode *n) {
    assert(n != NULL);
    assert(n->remp != NULL);
    
    DEBUG_PRINT((FDEBUG, "rec eq %d %d\n", n->nid, n->remp->nid));
    
    if((n->remp)->removed == 1)
        return (get_equal_node(n->remp));
    else
        return (n->remp);
}

static void merge(heap_mg *heap, evnode *x1, evnode *x2, unsigned int rec, ntrie *tail) {
    int i;
    evnode *tmp;
    ntrieNode *tmp_n, *node_nt;
    inward_n *nd, *tmp_node;
    
    heap_mg_el *hel;
    ntrieNode *nt_x1, *nt_x2, *tmp_tail;
    
    if (x1->deg > x2->deg) {
        tmp = x2;
        x2 = x1;
        x1 = tmp;
    }
    
    /* recursive end*/
    if(x1 == x2)
    {
        DEBUG_PRINT((FDEBUG, "==> x1: %d and x2: %d are equal.\n", x1->nid, x2->nid));
        /*mexPrintf("==>> EQUAL x1 and x2\n");*/
        return;
    }
    
    DEBUG_PRINT((FDEBUG, "--> merge: %d <-- %d [%u] |", x1->nid, x2->nid, rec));
    /*mexPrintf("==>> merge: %d <-- %d [%u] |", x1->nid, x2->nid, rec);*/
    
    NEDTRIE_FOREACH(tmp_tail, ntrie_s, tail) {
        /*mexPrintf("%d ", tmp_tail->key);*/
        DEBUG_PRINT((FDEBUG, "%d ", tmp_tail->key));
    }
    DEBUG_PRINT((FDEBUG, "|\n"));
    /*mexPrintf("|\n");*/
    
    /* Add x1 and x2 elements to the tail*/
    nt_x1 = pt_create_node_nt2(x1->nid);
    nt_x2 = pt_create_node_nt2(x2->nid);
    
    if (NEDTRIE_FIND(ntrie_s, tail, nt_x1) != NULL || NEDTRIE_FIND(ntrie_s, tail, nt_x2) != NULL)
    {
        DEBUG_PRINT((FDEBUG, "==> (%d,%d) are inserted into heap.\n", x1->nid, x2->nid));
        /*mexPrintf("====>> Insert into heap\n");*/
        
        NEDTRIE_INSERT(heap_mg_s, heap, create_heap_mg_el(heap, x1, x2));
        
        free(nt_x1);
        free(nt_x2);
        
        return;
    }
    
    x2->removed = 1;
    x2->remp = x1;
    
    NEDTRIE_INSERT(ntrie_s, tail, nt_x1);
    NEDTRIE_INSERT(ntrie_s, tail, nt_x2);
    
    /* INWARD SET*/
    /* --------------------------------------------------------------------*/
    if (x2->inward->n > 0) {
        /*mexPrintf("Sizeof inward set: %d\n", x2->inward->n);*/
        for(i=0, nd=x2->inward->firstNode; nd != NULL /*&& i<x2->inward->n*/; nd=tmp_node, i++) {
            tmp_node = nd->next;
            
            /*mexPrintf("Remove element of inward set: pointer (%p); state id (%d); size of inward set (%d)\n", nd, nd->data->node->nid, x2->inward->n);*/
            
            dll_inward_remove(x2->inward, nd);
            
            /* if deleted*/
            /*if(nd->data->rem == 0) { */
                dll_inward_insertend(x1->inward, nd);
                pt_change_node_nt(nd->data, x1);
            /*}*/
        }
    }
    
    /* CHILD SET*/
    /* --------------------------------------------------------------------*/
    if (x2->child->count > 0) {
        /*for(node_nt = NEDTRIE_MIN(ntrie_s, x2->child); node_nt != NULL; node_nt = tmp_node_nt) {
            tmp_node_nt = NEDTRIE_NEXT(ntrie_s, x2->child, node_nt);
            
            DEBUG_PRINT((FDEBUG, "Remove %d:%d\n", node_nt->node->nid, node_nt->key));
            //printf("Remove %d from child %p: %p, %u\n", node_nt->node->nid, node_nt->node->child, node_nt, node_nt->key);
            
            NEDTRIE_REMOVE(ntrie_s, x2->child, node_nt);
            
            tmp_n = NEDTRIE_FIND(ntrie_s, x1->child, node_nt);
            
            if (tmp_n == NULL)
                NEDTRIE_INSERT(ntrie_s, x1->child, node_nt);
            else // if (tmp_n != NULL)
            {
               merge(heap, tmp_n->node, node_nt->node, rec+1, tail);
               
            }
        }*/
        
        node_nt = NEDTRIE_MIN(ntrie_s, x2->child);
        while(node_nt != NULL) {
            
            DEBUG_PRINT((FDEBUG, "Remove %d:%d\n", node_nt->node->nid, node_nt->key));
            /*printf("Remove %d from child %p: %p, %u\n", node_nt->node->nid, node_nt->node->child, node_nt, node_nt->key);*/
            
            NEDTRIE_REMOVE(ntrie_s, x2->child, node_nt);
            
            tmp_n = NEDTRIE_FIND(ntrie_s, x1->child, node_nt);
            
            if (tmp_n == NULL)
                NEDTRIE_INSERT(ntrie_s, x1->child, node_nt);
            else /* if (tmp_n != NULL)*/
               merge(heap, tmp_n->node, node_nt->node, rec+1, tail);
            
            node_nt = NEDTRIE_MIN(ntrie_s, x2->child);
        }
    }
    
    NEDTRIE_REMOVE(ntrie_s, tail, nt_x1);
    NEDTRIE_REMOVE(ntrie_s, tail, nt_x2);
    
    /*work with heap*/
    while (heap->count > 0) {
        hel = NEDTRIE_MIN(heap_mg_s, heap);
        
        nt_x1->key = hel->x1->nid;
        nt_x2->key = hel->x2->nid;
        
        if (NEDTRIE_FIND(ntrie_s, tail, nt_x1) != NULL || NEDTRIE_FIND(ntrie_s, tail, nt_x2) != NULL)
            break;
        
        DEBUG_PRINT((FDEBUG, "++> Retrieve from heap N: %u, %d <- %d.\n", hel->key, hel->x1->nid, hel->x2->nid));
        /*printf("Heap-mg: %p, %u, %d -> %d\n", hel, hel->key, hel->x1->nid, hel->x2->nid);*/

        NEDTRIE_REMOVE(heap_mg_s, heap, hel);
        
        if (hel->x1->removed == 1) {
            DEBUG_PRINT((FDEBUG, "..>The node to merge %d is merged. The equal node is: %d.\n", hel->x1->nid, (get_equal_node(hel->x1))->nid));
            /*Get the equal node*/
            hel->x1 = get_equal_node(hel->x1);
        }
        
        if (hel->x1->removed == 0 && hel->x2->removed == 0) {
            merge(heap, hel->x1, hel->x2, rec+1, tail);
        }
        
        /* remove heap element*/
        destroy_heap_mg_el(hel);
    }
    
    free(nt_x1);
    free(nt_x2);
    
}

static void similarity(psa *trie, cluster_l **array_cluster_list, unsigned int size, int *eq_nodes) {
    unsigned int i;
    double hfit, pfit, kfit;
    cluster_l *cluster_list;
    cluster_n *cluster_node, *cluster_node_plus, *t_cluster_node_plus;
    
    ntrieNode *x, *y;
    setnt_l *list_ntrienodes;
    setnt_n *node_ntrienode, *set_node_ntrienode_tmp;
    
    double alpha = 0.000000000000001; /*  1.0000e-015*/
    double pv = 0.2;
    
    /* For all clusters except the last cluster when nodes are leafs*/
    for(i=0; i<size; i++) {
        cluster_list = array_cluster_list[i];
        
        if(cluster_list->firstNode->data->child->count < 1)
            continue;
        
        /* For all elements of cluster*/
        for (cluster_node = cluster_list->firstNode; cluster_node != NULL; cluster_node = cluster_node->next) {
            
            /* It checks which events are equal to others */
            if (cluster_node->data->removed == 1)
                continue;
            
            for(cluster_node_plus = cluster_node->next; cluster_node_plus != NULL; cluster_node_plus = t_cluster_node_plus) {
                t_cluster_node_plus = cluster_node_plus->next;
                
                /* Test if nodes are removed */
                if (cluster_node_plus->data->removed == 1)
                    continue;
                
                list_ntrienodes = dll_setnt_newlist();
                /* Copy child node pointer to list */
                NEDTRIE_FOREACH(y, ntrie_s, cluster_node_plus->data->child) {
                	/*printf("%p, %u\n", y, y->key);*/
                	dll_setnt_insertend(list_ntrienodes, dll_setnt_newnode(y));
                }
                
                /*DEBUG_PRINT((FDEBUG, "bijective comparison: set1: %d, set2: %d\n", cluster_node->data->child->count, list_ntrienodes->n));*/
                if (cluster_node->data->child->count != cluster_node_plus->data->child->count)
                    continue;
                
                assert(cluster_node->data->child->count == list_ntrienodes->n && cluster_node->data->child->count != 0 && list_ntrienodes->n != 0);
                
                /* Compare if two nodes have the same children set*/
                NEDTRIE_FOREACH(x, ntrie_s, cluster_node->data->child) {
                    /*printf("%p, %u\n", x, x->key);*/
                    
                    /*if(x->clks_size < 5)*/
                    /*    break;*/
                    
                    for(node_ntrienode = list_ntrienodes->firstNode; node_ntrienode != NULL; node_ntrienode = set_node_ntrienode_tmp) {
                        set_node_ntrienode_tmp = node_ntrienode->next;
                        
                        /*mexPrintf("%d - %d\n", x->node->eid, vecnode->data->eid);*/
                        /*if(node_ntrienode->data->clks_size < 5)*/
                        /*    continue;*/
                        
                        K_S_test(x->clks, x->clks_size, node_ntrienode->data->clks, node_ntrienode->data->clks_size, alpha, &hfit, &pfit, &kfit);
                        /*mexPrintf("Kolmogorov smirnof test executed ...\n");*/
                        /*mexPrintf("H:%f, P:%f, K:%f - (%d i:%d vs. %d i:%d)\n", hfit, pfit, kfit, x->clks_size, cluster_node->data->nid, node_ntrienode->data->clks_size, cluster_node_plus->data->nid);*/
                        
                        if ((hfit == 0) /*&& (pfit > pv)*/) {
                            dll_setnt_freenode(dll_setnt_remove(list_ntrienodes, node_ntrienode));
                            break;
                        }
                    }
                }
                
                /* If equal child set then merge states*/
                if (list_ntrienodes->n == 0) {
                    /*mexPrintf("Merge equal states %d,%d ...\n", cluster_node->data->nid, cluster_node_plus->data->nid);*/
                    (*eq_nodes)++;
                    
                    DEBUG_PRINT((FDEBUG, "Node %d and %d are equal, N: %d.\n", cluster_node->data->nid, cluster_node_plus->data->nid, *eq_nodes));
                    /*mexPrintf("------------ EQ node: %d\n",*eq_nodes);*/
                    
                    /*if (*eq_nodes < 6) {*/
                    /* MERGE - Find maximal degree of both nodes*/
                    merge(trie->h_mg, cluster_node->data, cluster_node_plus->data, 0, pt_create_nt());
                    
                    /*}*/
                    
                    dll_cluster_freenode(dll_cluster_remove(cluster_list, cluster_node_plus));
                }
                dll_setnt_freelist(list_ntrienodes);
            }
        }
    }
}

static void split(evnode **orderedNodes, unsigned int on_size, cluster_l ***aln, unsigned int *n_subset) {
    unsigned int i, n_set;
    evnode *tmp;
    cluster_l **arrayOfList_nodes;
    cluster_n *cls;
    
    /* Split the ordered nodes in independent lists */
    tmp = orderedNodes[0];
    n_set = 1;
    
    /* Create array of Lists */
    arrayOfList_nodes = (cluster_l **) malloc(sizeof(cluster_l *) * on_size);
    
    arrayOfList_nodes[n_set-1] = dll_cluster_newlist(); /* Initialize */
    dll_cluster_insertend(arrayOfList_nodes[n_set-1], dll_cluster_newnode(orderedNodes[0]));
    
    for(i=1; i < on_size; i++) {
        /*if (evnodecmp_c(orderedNodes[i], tmp) != 0) {*/
        if (orderedNodes[i]->child->count != tmp->child->count) {
            /* Create the set */          
            n_set++;
            arrayOfList_nodes[n_set-1] = dll_cluster_newlist(); /* Initialize next */
            
            tmp = orderedNodes[i];
        }
        
        /* Add nodes to clusters */
        dll_cluster_insertend(arrayOfList_nodes[n_set-1], dll_cluster_newnode(orderedNodes[i]));
    }
    
    arrayOfList_nodes = realloc(arrayOfList_nodes, sizeof(cluster_l *) * n_set);
    
    
    /* Debug */
    mexPrintf("Cluster DEBUG +++++++++++++++++++++++++++++++++++++++++\n");
    for(i=0; i<n_set; i++) {
        mexPrintf("Cluster %d\n", i);
        cls = arrayOfList_nodes[i]->firstNode;
        while(cls != NULL) {
            mexPrintf("%d ", cls->data->nid);
            
            cls = cls->next;
        }
        mexPrintf("\n");
    }
    mexPrintf("Cluster END DEBUG\n");
    
    *aln = arrayOfList_nodes;
    *n_subset = n_set;
}

static int cmp_evnode(const void *p1, const void *p2) {
    
    return evnodecmp_c(* (evnode * const *) p1, * (evnode * const *) p2);
}

/* 
 * This function 'select_non_removed_node' select the non removed nodes
 * in the prefix trie.
 */
static void select_non_removed_nodes(psa *trie, evnode ***out_array, unsigned int *size) {
    unsigned int i, n_active_nodes_on_trie;
    evnode **active_nodes_on_trie;
    
    active_nodes_on_trie = malloc(sizeof(evnode *) * trie->n);
    
    /*memcpy(orderedNodes, trie->nodeArray, sizeof(evnode *) * trie->n);*/
    for(i=0, n_active_nodes_on_trie=0; i<trie->n; i++) {
        if(trie->nodeArray[i]->removed == 0)
            active_nodes_on_trie[n_active_nodes_on_trie++] = trie->nodeArray[i];
    }
    
    DEBUG_PRINT((FDEBUG, "Selected %d from %d nodes of prefix tree\n", n_active_nodes_on_trie, trie->n));
    
    *size = n_active_nodes_on_trie;
    *out_array = active_nodes_on_trie;
}

/*
 * The probabilistic similarity of states function 'pss'.
 */
void pss(psa *trie) {
    unsigned int n_clusters, n_ordered_nodes;
    evnode **ordered_nodes;
    cluster_l **clusters_of_nodes;
    
    /* It verifies the similarity for each set of equal nodes */
    unsigned int eq_nodes = 0, eq_nodes_previously = 1;
    
    DEBUG_PRINT((FDEBUG, "Starting PSS function\n"));
    mexPrintf("Start PSS algorithm ... \n");
    
    /* While not have nodes to merge*/
    while(eq_nodes_previously != eq_nodes)
    {
        eq_nodes_previously = eq_nodes;
        
        select_non_removed_nodes(trie, &ordered_nodes, &n_ordered_nodes);
        
        /* It ordering trie nodes with quick short method (n*log(n)) */
        /* All nodes are sorted by number of childrens and children id's */
        qsort(ordered_nodes, n_ordered_nodes, sizeof(evnode *), cmp_evnode);
        
        /*pt_debug_trieNodes(trie);*/
        
        split(ordered_nodes, n_ordered_nodes, &clusters_of_nodes, &n_clusters);
        
        /* PSS*/
        similarity(trie, clusters_of_nodes, n_clusters, &eq_nodes);
    }
    
    /* Statistics */
    mexPrintf("+ EqualNodes: %d\n", eq_nodes);
}
